/*
   @Copyright:LintCode
   @Author:   tjyemail
   @Problem:  http://www.lintcode.com/problem/tower-of-hanoi
   @Language: C++
   @Datetime: 19-03-12 14:48
   */

class Solution {
public:
	/**
	 * @param n: the number of disks
	 * @return: the order of moves
	 */
	string tower[3]={"A","B","C"};
	vector<string> towerOfHanoi(int n) {
		// write your code here
		vector<string> vs;
		hanoi(n,0,1,2,vs);
		return vs;
	}
	void hanoi(int n, int start, int tmp, int end, vector<string> &vs){
		if (n==1){
			vs.push_back("from "+tower[start]+" to "+tower[end]);
			return;
		}
		hanoi(n-1,start,end,tmp,vs);
		hanoi(1,start,tmp,end,vs);
		hanoi(n-1,tmp,start,end,vs);
	}
};
